package linked;

import java.util.HashSet;
import java.util.Set;

/**
 * 160. 相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null 。
 * <p>
 * 题目数据 保证 整个链式结构中不存在环。
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 */
public class Problem_160 {

    /**
     * 方法一：哈希集合
     * 判断两个链表是否相交，可以使用哈希集合存储链表节点。
     * 首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。
     * 然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。
     * 如果某个节点在哈希集合中，则表明此节点就是两个链表相交的起始节点，直接返回此节点。
     * 如果链表 headB 中的所有节点都不在哈希集合中，则表明两个链表不相交，此时返回 null。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode listNodeA = headA;
        ListNode listNodeB = headB;

        while (listNodeA != null) {
            set.add(listNodeA);
            listNodeA = listNodeA.next;
        }

        while (listNodeB != null) {
            if (set.contains(listNodeB)) {
                return listNodeB;
            }
            listNodeB = listNodeB.next;
        }

        return null;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
